%  Copyright (C) 2002 Regents of the University of Michigan, portions used with permission 
%  For more information, see http://csem.engin.umich.edu/tools/swmf
\section{Grid \label{section:grid}}
\subsection{Block Structure \label{section:blocks}}

\BATSRUS\ uses a block based, adaptive grid that allows the user to
specify where he or she wants more resolution or to let the code
determine where more resolution is needed.  This is one of the
most advantageous features of the \BATSRUS\ code.  While other codes
use non-Cartesian meshes, they are often tuned to a
very specific instance of a specific problem.  \BATSRUS\ uses
a highly parallelizable, adaptable grid which is suited to a wide 
variety of problems.

Mesh refinement techniques that adapt the computational
grid to the solution of the governing PDEs can be very effective in treating
problems with disparate length scales.   Methods of this type avoid
under resolving the solution in regions deemed of interest (e.g., high-gradient
regions) and, conversely, avoid over resolving the solution in other less
interesting regions (low-gradient regions), thereby saving orders of
magnitude in computing resources for many problems.  For typical solar wind
flows, length scales can range from tens of kilometers in the near Earth region
to the Earth-Sun distance ($1.5\times10^{11}$ m), and time scales can range from
a few seconds near the Sun to the expansion time of the solar wind from the Sun
to the Earth ($\sim$$10 ^5$ s).  The use of a mesh containing varying
size cells is extremely beneficial and
almost a virtual necessity for solving problems with such disparate spatial and
temporal scales.

Keeping in mind
the desire for high performance on massively parallel computer architectures, a
relatively simple yet effective block-based AMR technique has been developed.
Here the governing equations are
integrated to obtain volume-averaged solution quantities within blocks
of rectangular Cartesian computational cells.  
The computational cells are embedded
in regular structured blocks of equal sized cells.  The blocks are
geometrically self-similar with dimensions $\tilde{\ell}_x \times
\tilde{\ell}_y \times \tilde{\ell}_z$ and consist of $N_x \times N_y \times
N_z$ cells, where $\tilde{\ell}_x$, $\tilde{\ell}_y$, and $\tilde{\ell}_z$ are
the nondimensional lengths of the sides of the rectangular blocks and $N_x$,
$N_y$, and $N_z$ are even, but not necessarily all equal, integers. Typically,
blocks consisting of anywhere between $4 \times 4 \times 4 = 64$ and $12 \times
12 \times 12 = 1728$ cells are used.  Solution
data associated with each block are stored in standard indexed array data
structures.  It is therefore straightforward to obtain solution information
from neighboring cells within a block.

Computational grids are then composed of many self-similar blocks. Although
each block within a grid has the same data storage requirements, blocks may be
of different sizes in terms of the volume of physical space that they
occupy (see Figure~\ref{fig:blocks}).
Starting with an initial mesh consisting of blocks of equal size (i.e., equal
resolution), adaptation is accomplished by the dividing and coarsening of
appropriate solution blocks (see Figure~\ref{fig:refine_coarsen}).  In regions
requiring 
increased cell resolution, a
``parent'' block is refined by dividing itself into eight ``children'' or
``offspring.''  Each of the eight octants of a parent block becomes a new block
having the same number of cells as the parent and thereby doubling the cell
resolution in the region of interest. Conversely, in regions that are deemed
overresolved, the refinement process is reversed, and eight children are
coarsened and coalesced into a single parent block.  In this way, the cell
resolution is reduced by a factor of 2. Standard multigrid-type restriction
and prolongation operators are used to evaluate the solution on all blocks
created by the coarsening and division processes, respectively.
\begin{figure}
\begin{center}
\includegraphics*[width=8.4cm]{adaptiveblock.pdf}
\end{center}
\caption{(left) Self-similar blocks used in parallel block-based AMR
           scheme. (right) Self-similar blocks illustrating the double
           layer of ghost cells for both coarse and fine blocks.}
\label{fig:blocks}
\end{figure}
\begin{figure}
\begin{center}
\includegraphics*[width=8.4cm]{adapted_grid.pdf}
\end{center}
\caption{2D example of the refining and coarsening of blocks that are
4x4 cells in size.}
\label{fig:refine_coarsen}
\end{figure}

Two neighboring blocks, one of which has been refined and one of which has not,
are shown in Figure~\ref{fig:blocks}.  Any of the blocks shown in
Figure~\ref{fig:blocks} can in turn be refined, and so on, leading to successively
finer blocks. In the present method, mesh refinement is constrained such that the
cell resolution changes by only a factor of 2 between adjacent blocks and such
that the minimum resolution is not less than that of the initial mesh.
In order that the update scheme for a given iteration or time step can be
applied directly to all blocks in an independent manner, some additional
solution information is shared between adjacent blocks having common
interfaces.  This information is stored in an additional two layers of
overlapping ``ghost'' cells associated with each block  as shown in
Figures~\ref{fig:blocks}, \ref{fig:message_pass_equal} and 
\ref{fig:message_pass_res_change}.  At interfaces between blocks of
equal 
resolution (see Figure~\ref{fig:message_pass_equal}) these
ghost cells are simply assigned the solution values associated with the
appropriate interior cells of the adjacent blocks.  At resolution
changes (see Figure~\ref{fig:message_pass_res_change}),
restriction and prolongation operators, similar to those used in block
coarsening and division, are employed to evaluate the ghost cell solution
values.  After each stage of the multistage time-stepping algorithm, ghost
cell values are reevaluated to reflect the updated solution values of
neighboring blocks.  With the AMR approach, additional interblock
communication is also required at interfaces with resolution changes to
strictly enforce the flux conservation properties of the finite-volume
scheme (see section~\ref{section:finite_volume}).
\begin{figure}
\begin{center}
\includegraphics*[width=8.4cm]{message_pass_equal.pdf}
\end{center}
\caption{Computational cells and ghost cells for two
neighboring blocks of the same resultion.  Shaded cells indicate
how ghost cells are filled from computational cells in the neighboring block.}
\label{fig:message_pass_equal}
\end{figure}
\begin{figure}
\begin{center}
\includegraphics*[width=8.4cm]{message_pass_res_change.pdf}
\end{center}
\caption{Computational cells and ghost cells for two
neighboring blocks of the different resultion.  Shaded cells indicate
how ghost cells are filled from computational cells in the neighboring block.}
\label{fig:message_pass_res_change}
\end{figure}

The division of blocks into children creates a very hierarchical
relation for blocks in the grid.  This structure, called an ``octree''
because each block is divided into eight children, can be used to
easily find neighboring blocks.

With AMR, as with any numerical implemention, there are trade-offs to
be considered.  Larger blocks have a lower ghost cell
to computational cell ratio than smaller blocks.  A 12x12x12 block has
a ratio of 1.37 while a 4x4x4 block has a ratio of 7.  This means that 
larger blocks have less ``wasted'' memory.  In addition, 
with larger blocks, message passing communication time may be less.
However, when doing
refinement larger blocks tend to resolve not only the desired feature
but other nearby areas, thereby using more cells than necessary.
See also the discussion in the section on ``Setting Grid Structure''
in the USER MANUAL.


\subsection{Adaptive Mesh Refinement (AMR) \label{sectio:amr}}

One of the advantages of this hierarchical data structure is that it
is relatively easy to carry out local mesh refinement at anytime during a
calculation.  If, at some point in a computation, a particular region of the
flow is deemed to be sufficiently interesting, better resolution of that region
can be attained by refining the solution blocks in that region, without
affecting the grid structure in other regions of the flow. Reducing the grid
resolution in a region is equally easy (see Figure~\ref{fig:refine_coarsen}). 
\BATSRUS\ allows the user to specify multiple physics based criteria 
to direct the coarsening and division of blocks. In particular,
decisions as to when to refine or coarsen blocks
are made based on comparisons of the maximum values of various local flow
quantities determined in each block to specified refinement threshold values.
As an example, three typical flow quantities or refinement criteria, $\epsilon_k$,
have the forms
%%
\begin{equation} \label{eq:refine.criteria}
\epsilon_1 \propto \left| {\bf \nabla} \cdot  \mbox{\bf u}
\right| \quad				      
\epsilon_2 \propto \left| {\bf \nabla} \times \mbox{\bf u}
\right| \quad				      
\epsilon_3 \propto \left| {\bf \nabla} \times \mbox{\bf B}
\right| \,.
\end{equation}
%%
These quantities represent local measures of the compressibility and vorticity
of the plasma as well as the electric current density.
Note that the refinement thresholds are
dynamically adjusted so as to exercise control over the total numbers of
blocks, and hence cells, used in a calculation.

Adaptive mesh refinement, or AMR, is one of main features of \BATSRUS.  It allows
the user to create a mesh which has the desired number of cells, but which also
resolves the features of interest.

